Communications in Combinatorics and Optimization
Volume:9 Issue: 1, Winter 2024

In a graph $G$ of minimum degree $\delta$ and maximum degree $\Delta$, a subset $S$ of vertices of $G$ is $j$-independent, for some positive integer $j,$ if every vertex in $S$ has at most $j-1$ neighbors in $S$. The $j$-independence number $\beta_{j}(G)$ is the maximum cardinality of a $j$-independent set of $G$. We first establish an inequality between $\beta_{j}(G)$ and $\beta_{\Delta}(G)$ for $1\leq j\leq\delta-1$. Then we characterize all graphs $G$ with $\beta_{j}(G)=\beta_{\Delta}(G)$ for $j\in\{1,\dots,\Delta-1\}$, where the particular cases $j=1,2,\delta-1$ and$\delta$ are well distinguished.

A generic rectangular partition   is a partition of a rectangle into a finite number of rectangles provided that no four of them meet at a point.  A graph $\mathcal{H}$ is called  dual of a plane graph $\mathcal{G}$ if there is one$-$to$-$one correspondence between the vertices of $\mathcal{G}$ and the regions of $\mathcal{H}$, and  two vertices of $\mathcal{G}$ are adjacent if and only if the corresponding regions of $\mathcal{H}$ are adjacent. A plane graph is a  rectangularly dualizable graph  if its dual  can be embedded as a  rectangular partition.   A rectangular dual  $\mathcal{R}$ of a plane graph $\mathcal{G}$ is a partition of a  rectangle  into $n-$rectangles such that (i) no four rectangles of $\mathcal{R}$ meet at a point, (ii)  rectangles in  $\mathcal{R}$ are mapped to vertices of $\mathcal{G}$,  and (iii)  two rectangles in $\mathcal{R}$ share a common boundary segment if and only if the corresponding vertices are adjacent in $\mathcal{G}$. In this paper, we derive a necessary and sufficient  for a rectangularly dualizable graph $\mathcal{G}$ to admit a unique rectangular dual upto combinatorial  equivalence. Further we show that $\mathcal{G}$ always admits   a slicible as well as an area$-$universal  rectangular dual.

Let $G=(V,E)$, $V=\{v_1,v_2,\ldots,v_n\}$, $E=\{e_1,e_2,\ldots, e_m\}$, be a simple graph of order $n\ge 2$ and size $m$ without isolated vertices. Denote with $\mu_1\ge \mu_2\ge \cdots \ge \mu_{n-1}>\mu_n=0$ the Laplacian eigenvalues of $G$. The Kirchhoff index of a graph $G$,  defined in terms of Laplacian eigenvalues, is given as $Kf(G) = n \sum_{i=1}^{n-1}\frac{1}{\mu_i}$. Some new lower bounds on $Kf(G)$ are obtained.

A graph $G$ of order $n$ is called $k-$step Hamiltonian for $k\geq 1$ if we can label the vertices of $G$ as $v_1,v_2,\ldots,v_n$ such that $d(v_n,v_1)=d(v_i,v_{i+1})=k$ for $i=1,2,\ldots,n-1$. The (vertex) chromatic number of a graph $G$ is the minimum number of colors needed to color the vertices of $G$ so that no pair of adjacent vertices receive the same color. The clique number of $G$ is the maximum cardinality of a set of pairwise adjacent vertices in $G$. In this paper, we study the chromatic number and the clique number in $k-$step Hamiltonian graphs for $k\geq 2$. We present upper bounds for the chromatic number in $k-$step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in $k-$step Hamiltonian graphs and characterize graphs achieving equality of the bound.

For a graph $G$ with chromatic number $k$, a dominating set $S$ of $G$ is called a chromatic-transversal dominating set (ctd-set) if $S$ intersects every color class of any $k$-coloring of $G$.  The minimum cardinality of a ctd-set of $G$ is called the {\em chromatic transversal domination number} of $G$ and is denoted by $\gamma_{ct}(G)$.  A {\em Roman dominating function} (RDF) in a graph $G$ is a function $f : V(G) \to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$.  The weight of a Roman dominating function is the value $w(f) = \sum_{u \in V} f(u)$.  The minimum weight of a Roman dominating function of a graph $G$ is called the {\em Roman domination number} of $G$ and is denoted by $\gamma_R(G)$.  The concept of {\em chromatic transversal domination} is extended to Roman domination as follows:   For a graph $G$ with chromatic number $k$, a {\em Roman dominating function} $f$ is called a {\em chromatic-transversal Roman dominating function} (CTRDF) if the set of all vertices $v$ with $f(v) > 0$ intersects every color class of any $k$-coloring of $G$.  The minimum weight of a chromatic-transversal Roman dominating function of a graph $G$ is called the {\em chromatic-transversal Roman domination number} of $G$ and is denoted by $\gamma_{ctR}(G)$.  In this paper a study of this parameter is initiated.

An element $i=(v,e)$ of a graph $G$ is called  an incidence of $G$, if $v\in V(G)$, $e\in E(G)$ and $v\in e$. The simultaneous coloring of vertices and incidences of a graph is coloring  the vertices and incidences of the graph properly at the same time such that any two adjacent or incident elements receive distinct colors. In this paper, we investigate the simultaneous coloring of vertices and incidences of hypercubes.

A subset $D$ of the vertex set $V(G)$ in a graph $G$ is a point-set dominating set (or, in short, psd-set) of $G$ if for every set $S\subseteq V- D$, there exists a vertex $v\in D$ such that the induced subgraph $\langle S\cup \{v\}\rangle$ is connected.  The minimum cardinality of a psd-set of $G$ is called the point-set domination number of $G$. In this paper, we establish two sharp lower bounds for point-set domination number of a graph in terms of its diameter and girth. We characterize graphs for which lower bound of point set domination number is attained in terms of its diameter. We also establish an upper bound and give some classes of graphs which attains the upper bound of point set domination number.

In [On extremal multiplicative Zagreb indices of trees with given domination number, Applied Mathematics and Computation 332 (2018), 338--350] Wang et al. presented bounds on the multiplicative Zagreb indices of trees with given domination number. We fill in the gaps in their proofs of Theorems 3.1 and 3.3 and we correct Theorem 3.3.

Operations in the theory of graphs has a substantial influence in the analytical and factual dimensions of the domain. In the realm of chemical graph theory, topological descriptor serves as a comprehensive graph invariant linked with a specific molecular structure. The study on the Sombor index is initiated recently by Ivan Gutman. The triangle parallel graph comprises of the edges of subdivision graph along with the edges of the original graph. In this paper, we make use of combinatorial inequalities related with the vertices, edges and the neighborhood concepts as well as the other topological descriptors in the computations for the determination of bounds of Sombor index for certain corona products involving the triangle parallel graph.

Let $G=(V, E)$ be a simple graph such that $\lambda_1, \ldots, \lambda_n$ be the eigenvalues of $G$. The energy of graph $G$ is denoted by $E(G)$ and is defined as $E(G)=\sum_{i=1}^{n}|\lambda_{i}|$. The edge energy of $G$ is the energy of line graph $G$. In this paper, we investigate the energy and edge energy for two Cayley graphs on the abelian group $\mathbb{Z}_{n}^{4}$, namely, the Sudoku graph and the positional Sudoku graph. Also, we obtain graph energy and edge energy of the complement of these two graphs.

A defective vertex coloring of a graph is a coloring in which some adjacent vertices may have the same color. An edge whose adjacent vertices have the same color is called a bad edge. A defective coloring of a graph $G$ with minimum possible number of bad edges in $G$ is known as a near proper coloring of $G$.  In this paper, we introduce the notion of equitable near proper coloring of graphs and determine the minimum number of bad edges obtained from an equitable near proper coloring of some graph classes.

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not its arc set. In this paper, we study  all tetravalent half-arc-transitive graphs of order $12p$,  where $p$ is a prime.

A quasi total double Roman dominating function (QTDRD-function) on a graph $G=(V(G),E(G))$ is a function $f:V(G)\longrightarrow\{0,1,2,3\}$ having the property that \textrm{(i)} if $f(v)=0$, then vertex $v$ must have at least twoneighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$; \textrm{(ii)} if $f(v)=1$, then vertex $v$ has at least one neighbor $w$ with $f(w)\geq2$, and \textrm{(iii)} if $x$ is an isolated vertex in the subgraph induced by the set of vertices assigned non-zero values, then $f(x)=2$. The weight of a QTDRD-function $f$ is the sum of its function values over the whole vertices, and the quasi total double Roman domination number $\gamma_{qtdR}(G)$ equals the minimum weight of a QTDRD-function on $G$. In this paper, we show that for any tree $T$ of order $n\ge 4$, $\gamma_{qtdR}(T)\le n+\frac{s(T)}{2}$, where $s(T)$ is the number of support vertices of $T$,  that improves a known bound.

The index of a signed graph is the largest eigenvalue of its adjacency matrix. Let $\mathfrak{U}_{n,k,4}$ be the set of all signed complete graphs of order $n$ whose negative edges induce a unicyclic graph of order $k$ and girth at least $4$. In this paper, we identify the signed graphs achieving the maximum index in the class $\mathfrak{U}_{n,k,4}$.

The concept of the Sombor indices of a graph was introduced by Gutman. A vertex-edge variant of the Sombor index of graphs is called the KG-Sombor index.  Recently, the Sombor and  KG-Sombor indices of Kragujevac trees were studied, and the extremal Kragujevac trees with respect to these indices were empirically  determined.   Here we give analytical proof of the results.